class Solution(object):
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        rows = len(matrix)
        cols = len(matrix[0])
        for r in range(rows):
            if matrix[r][0] > target:
                break
            for c in range(cols):
                if matrix[r][c] == target:
                    return True
                if matrix[r][c] > target:
                    cols = c
                    break
        return False
